#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2018/8/14 13:46
# @Author  : yangdy
# @Email   : yangdy@egu360.com
# @File    : 中级-奇偶链表.py
# @Software: PyCharm


# Definition for singly-linked list.


class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution(object):
    def oddEvenList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        h1, p1, h2, p2 = None, None, None, None
        i = 0
        p = head
        while p:
            if i % 2 == 0:
                if h1:
                    p1.next = p
                    p1 = p
                else:
                    h1 = p
                    p1 = p
            else:
                if h2:
                    p2.next = p
                    p2 = p
                else:
                    h2 = p
                    p2 = p
            p = p.next
            i += 1
        p1.next = h2
        p2.next = None
        return h1


def list_print(head):
    p = head
    out = ''
    while p:
        out += ('%d%s' % (p.val, ' -> ' if p.next else ''))
        p = p.next
    return out


def main():
    solve = Solution()

    a = [1, 2, 3, 4, 5]
    head, p = None, None
    for i in range(len(a)):
        if head:
            p.next = ListNode(a[i])
            p = p.next
        else:
            head = ListNode(a[i])
            p = head
    print('head:')
    print(list_print(head))
    ans = solve.oddEvenList(head)
    print('ans:')
    print(list_print(ans))


if __name__ == '__main__':
    main()
